/*
169. 求众数
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且数组中的众数永远存在。
*/
#include <vector>
using namespace std;
/**
 * 解法1：
 * conut计数，大于一半以上的就是答案
 */

class Solution
{
public:
    int majorityElement(vector<int> &nums)
    {
        if(nums.size() <= 2) return nums[0];
        int count = 0;
        int ret = nums[0];
        for(auto &c : nums) {
            if(ret != c) {
                count--;
                if(count <= 0) {
                    ret = c;
                    count = 1;
                }
            } else {
                count++;
            }
        }

        return ret;
    }
};